Skip to main content

Table of Contents

Heap / Priority Queue

TypeInsertSearch (Max only)Delete
Best CaseO(logn)O(1)O(logn)
Average CaseO(logn)O(1)O(logn)
Worst CaseO(logn)O(1)O(logn)
  • A Max Heap is a tree data structure which is a bit more specific than a Binary Search Tree, the Max Heap structure has the largest node as the root node, and any node's children are less than it's node
  • Allows us to get the max item very quickly, and insert and delete operations involve potentially rotating some items but altogether are O(logn) for worst, average, and best cases since we still traverse a general tree structure